//
//  Problem1337.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/5.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1337. 矩阵中战斗力最弱的 K 行
 给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。
 请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
 如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
 军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。

 示例 1：
 输入：mat =
 [[1,1,0,0,0],
  [1,1,1,1,0],
  [1,0,0,0,0],
  [1,1,0,0,0],
  [1,1,1,1,1]],
     k = 3
     输出：[2,0,3]
     解释：
     每行中的军人数目：
     行 0 -> 2
     行 1 -> 4
     行 2 -> 1
     行 3 -> 2
     行 4 -> 5
     从最弱到最强对这些行排序后得到 [2,0,3,1,4]
 示例 2：
 输入：mat =
 [[1,0,0,0],
  [1,1,1,1],
  [1,0,0,0],
  [1,0,0,0]],
     k = 2
     输出：[0,2]
     解释：
     每行中的军人数目：
     行 0 -> 1
     行 1 -> 4
     行 2 -> 1
     行 3 -> 1
     从最弱到最强对这些行排序后得到 [0,2,3,1]
 提示：
     m == mat.length
     n == mat[i].length
     2 <= n, m <= 100
     1 <= k <= m
     matrix[i][j] 不是 0 就是 1
 */
@objcMembers class Problem1337: NSObject {
    func solution() {
        print(kWeakestRows( [[1,1,0,0,0],
                             [1,1,1,1,0],
                             [1,0,0,0,0],
                             [1,1,0,0,0],
                             [1,1,1,1,1]], 3))
    }
    /*
     1: 遍历数组mat，通过二分法找出每一个行1的个数
     2: 存储每一行1的个数，然后排序
     */
    func kWeakestRows(_ mat: [[Int]], _ k: Int) -> [Int] {
        var l = 0
        var r = 0
        var mid = 0
        
        var list:[[Int]] = []
        for (i, row) in mat.enumerated() {
            l = 0
            r = row.count-1
            if row[r] == 1 {
                list.append([row.count,i])
                continue
            }
            while l<r {
                mid = l + (r - l) >> 1
                if row[mid] == 0 {
                    r = mid
                } else {
                    l = mid + 1
                }
            }
            list.append([l,i])
        }
        
        list.sort { (first, second) -> Bool in
            if first[0] == second[0] {
                return first[1] < second[1]
            } else {
                return first[0] < second[0]
            }
        }
        
        var result:[Int] = []
        for i in 0..<k {
            result.append(list[i][1])
        }
        
        return result
    }
}
